package com.leetcode.算法策略相关.回溯;

import lombok.Data;
import lombok.extern.slf4j.Slf4j;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @author: xiaomi
 * @date: 2022/5/21
 * @description: 问题描述：
 * 存在：
 * 1. 机型 Ma,Mb,Mc 三种；
 * 2. 模块 A,B,C,D 四种；
 * 3. 物料 a1,a2,a3,a4 四种
 * 有以下关系：
 * 1. Ma=7A+5B
 * 2. Mb=5B+3C
 * 3. Mc=3C+7D
 * 4. A=5a1+6a2
 * 5. B=4a2+3a3
 * 6. C=6a1+4a3
 * 7. D=3a2+2a4
 * 求：现有 a1,a2,a3,a4各 size 个，能得到的最大的Ma,Mb,Mc 和是多少？
 */
@Slf4j
public class BOMSatisfy {

    /**
     * 作为数据缓存
     * key:1-完成 Ma 机型数量.2-完成 Mb 机型数量.3-完成 Mc 机型数量
     * value:剩余材料的数量数组
     */
    private Map<String, int[]> cacheMap4Left = new HashMap<>();

    /**
     * 最后的结果，key 同上
     */
    private Map<String, Integer> resultMap = new HashMap<>();

    /**
     * 状态数组
     */
    private int[] statusArray = new int[]{1, 2, 3};

    /**
     * 表示每个状态所能支撑的最大数量
     */
    private int[] statusMaxNum = new int[3];
    //当前选择机型
    private int currentStatus = 1;

    //region  各个机型代表的各种物料的消耗

    private static final int[] machineFirstBOMArray = {35, 62, 15, 0};
    private static final int[] machineSecondBOMArray = {18, 20, 27, 0};
    private static final int[] machineThirdBOMArray = {18, 21, 12, 14};

    //endregion

    /**
     * 状态对应 BOMArray 的数组
     */
    private static Map<Integer, int[]> statusArrMap = new HashMap<>();


    /**
     * 分析：
     * 忽略中间层级，换算为机型和物料的关系：
     * Ma= 35a1+62a2+15a3
     * Mb= 18a1+20a2+27a3
     * Mc= 18a1+21a2+12a3+14a4
     *
     * @param args
     */
    public static void main(String[] args) {
        int size = 100;
        int[] materials = new int[]{size, size, size, size};
        int[] materials2 = new int[]{size, size, size, size};
        int[] materials3 = new int[]{size, size, size, size};
        int[] materials4 = new int[]{size, size, size, size};

        //1.测试排列
//        testArrange(materials);
        //2.测试组合
//        testCompose(materials2);
        //3.测试回溯的组合最优算法

        //4.DP 
        //testDP(materials4);

        //5.使用机型组合的方式！
        testMachineCompose(materials4);
    }

    private static void testArrange(int[] materials) {
        BOMSatisfy bomSatisfy = new BOMSatisfy();
        log.info("...排列...");
        bomSatisfy.solutionArrange(materials);
    }

    private static void testCompose(int[] materials) {
        BOMSatisfy bomSatisfy = new BOMSatisfy();
        log.info("...组合...");
        bomSatisfy.solutionCompose(materials);
    }

    private static void testDP(int[] materials) {
        BOMSatisfy bomSatisfy = new BOMSatisfy();
        log.info("...动态规划...");
        bomSatisfy.solutionDP(materials);
    }

    private static void testMachineCompose(int[] materials) {
        BOMSatisfy bomSatisfy = new BOMSatisfy();
        log.info("...优化组合...");
        bomSatisfy.solutionComposeMaximum(materials);
    }

    /**
     * 1.排列
     *
     * @param materials
     */
    public void solutionArrange(int[] materials) {
        TracePath tracePath = new TracePath();
        backTracing(materials, tracePath);

        int max = 0;
        //打印最后的结果
        for (Map.Entry<String, Integer> entry : resultMap.entrySet()) {
            //log.info(entry.getKey() + ":" + entry.getValue());
            System.out.println(entry.getKey() + ":" + entry.getValue());
            max = Math.max(max, entry.getValue());
        }
        //只打印最大的方案
        log.info("只打印最大的方案");
        for (Map.Entry<String, Integer> entry : resultMap.entrySet()) {
            if (entry.getValue() == max) {
                //log.info(entry.getKey() + ":" + entry.getValue());
                System.out.println(entry.getKey() + ":" + entry.getValue());
            }
        }
    }

    /**
     * 2.组合
     *
     * @param materials
     */
    public void solutionCompose(int[] materials) {
        TracePath tracePath = new TracePath();
        backTracingByCompose(materials, tracePath);

        int max = 0;
        //打印最后的结果
        for (Map.Entry<String, Integer> entry : resultMap.entrySet()) {
            //log.info(entry.getKey() + ":" + entry.getValue());
            System.out.println(entry.getKey() + ":" + entry.getValue());
            max = Math.max(max, entry.getValue());
        }
        //只打印最大的方案
        log.info("只打印最大的方案");
        for (Map.Entry<String, Integer> entry : resultMap.entrySet()) {
            if (entry.getValue() == max) {
                //log.info(entry.getKey() + ":" + entry.getValue());
                System.out.println(entry.getKey() + ":" + entry.getValue());
            }
        }
    }

    /**
     * 3.多维费用背包问题（暂时不考虑多重性）
     * 分析：影响背包使用完毕的维度，在目前条件下，是 a1,a2,a3,a4
     * 感觉效率非常低！
     *
     * @param materials
     */
    public void solutionDP(int[] materials) {
        int N = 3;
        int bomA1 = 100;
        int bomA2 = 100;
        int bomA3 = 100;
        int bomA4 = 100;

        int[] a1 = {0, 35, 62, 15, 0, 1};
        int[] a2 = {0, 18, 20, 27, 0, 1};
        int[] a3 = {0, 18, 21, 12, 14, 1};

        int[] bom1 = {0, 35, 18, 18};
        int[] bom2 = {0, 62, 20, 21};
        int[] bom3 = {0, 15, 27, 12};
        int[] bom4 = {0, 0, 0, 14};
        int[] value = {0, 1, 1, 1};


        int[][][][][] dp = new int[N + 1][bomA1 + 1][bomA2 + 1][bomA3 + 1][bomA4 + 1];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= bomA1; j++) {
                for (int k = 1; k <= bomA2; k++) {
                    for (int l = 1; l <= bomA3; l++) {
                        for (int m = 1; m <= bomA4; m++) {
                            if (j < bom1[i] || k < bom2[i] || l < bom3[i] || m < bom4[i]) {
                                // 客观条件限制，不能选择当前物品N
                                //dp[i][j][k] = dp[i - 1][j][k];
                                dp[i][j][k][l][m] = dp[i - 1][j][k][l][m];
                            } else {
//                                dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i][j - v[i]][k - m[i]] + w[i]);
                                dp[i][j][k][l][m] = Math.max(dp[i - 1][j][k][l][m],
                                        dp[i][j - bom1[i]][k - bom2[i]][l - bom3[i]][m - bom4[i]] + value[i]);
                            }
                        }
                    }
                }
            }
        }
        int max = dp[N][bomA1][bomA2][bomA3][bomA4];

    }

    /**
     * 4.以机型作为回溯的单位，最后的一个机型取最大数量
     *
     * @param materials
     */
    public void solutionComposeMaximum(int[] materials) {
        TracePath tracePath = new TracePath();
        int machineAMax = calcMaxNum(materials, machineFirstBOMArray);
        int machineBMax = calcMaxNum(materials, machineSecondBOMArray);
        int machineCMax = calcMaxNum(materials, machineThirdBOMArray);
        statusMaxNum[0] = machineAMax;
        statusMaxNum[1] = machineBMax;
        statusMaxNum[2] = machineCMax;
        //init map
        statusArrMap.put(1, machineFirstBOMArray);
        statusArrMap.put(2, machineSecondBOMArray);
        statusArrMap.put(3, machineThirdBOMArray);
        backTracingByComposeMaximum(materials, tracePath);
        int bbb=1;
    }

    /**
     * 排列纵向遍历
     *
     * @param materials
     * @param path      访问路径
     */
    private void backTracing(int[] materials, TracePath path) {
        //1. 终止条件：发现 materials 任一小于0
        if (hasRunOut(materials)) {
            //2.存放结果：此时并没有做资源的最大化，存储的条件只是因为超量了！
            int first = path.getMachineFirst();
            int second = path.getMachineSecond();
            int third = path.getMachineThird();
            int lastStatus = path.getLastMachineStatus();
            switch (lastStatus) {
                case 1:
                    first--;
                    break;
                case 2:
                    second--;
                    break;
                case 3:
                    third--;
                    break;
            }
            resultMap.put(generateKey(first, second, third), path.getCount() - 1);
            return;
        }

        //3.横向遍历：选择：本层集合中元素（树中节点孩子的数量就是集合的大小）
        for (int status : statusArray) {
            //拷贝一份路径
            //TracePath nPath = new TracePath(path.machineFirst,path.machineSecond,path.machineThird,path.deque);
            //4.处理节点
            //4.1 前进
            path.stepForward(status);
            //4.2 减去物料
            runMaterial(materials, status);
            //纵向遍历
            //递归
            backTracing(materials, path);
            //5.回溯，撤销处理结果
            backMaterial(materials, status);
            path.backOff();
        }
    }

    /**
     * 组合纵向遍历
     *
     * @param materials
     * @param path
     */
    private void backTracingByCompose(int[] materials, TracePath path) {
        //1. 终止条件：发现 materials 任一小于0
        if (hasRunOut(materials)) {
            //2.存放结果：此时并没有做资源的最大化，存储的条件只是因为超量了！
            int first = path.getMachineFirst();
            int second = path.getMachineSecond();
            int third = path.getMachineThird();
            int lastStatus = path.getLastMachineStatus();
            switch (lastStatus) {
                case 1:
                    first--;
                    break;
                case 2:
                    second--;
                    break;
                case 3:
                    third--;
                    break;
            }
            resultMap.put(generateKey(first, second, third), path.getCount() - 1);
            return;
        }
        //3.横向遍历：选择：本层集合中元素（树中节点孩子的数量就是集合的大小）
        for (int status : statusArray) {
            //剪枝：必须让下一个 Status >= 本 Status
            if (path.getCount() > 0 && status < path.getLastMachineStatus()) {
                continue;
            }
            //拷贝一份路径
            //TracePath nPath = new TracePath(path.machineFirst,path.machineSecond,path.machineThird,path.deque);
            //4.处理节点
            //4.1 前进
            path.stepForward(status);
            //4.2 减去物料
            runMaterial(materials, status);
            //纵向遍历
            //递归
            backTracing(materials, path);
            //5.回溯，撤销处理结果
            backMaterial(materials, status);
            path.backOff();
        }
    }

    /**
     * 追求最大数量的纵向遍历
     *
     * @param materials
     * @param path
     */
    private void backTracingByComposeMaximum(int[] materials, TracePath path) {
        //1. 终止条件：发现本次选择的机型已经到了最后一个
        if (currentStatus == 3) {
            //2.存放结果：此时并没有做资源的最大化，存储的条件只是因为超量了！
            int lastNum = calcMaxNum(materials, machineThirdBOMArray);
            resultMap.put(generateKey(path.getMachineFirst(), path.getMachineSecond(), lastNum), path.getCount() + lastNum);
            return;
        }

        //int num = statusMaxNum[currentStatus];
        //3.横向遍历：选择：本层集合中元素（树中节点孩子的数量就是集合的大小）
        int num = 0;
        while (true) {
            //4.处理节点
            if (num > 0) {
                if (!canUseByCurrentMaterials(materials, statusArrMap.get(currentStatus))) {
                    //如果剩下的都不能被用来生产一台
                    break;
                }
                //如果剩下的可以被用来生产一台

                //4.1 减去物料
                runMaterial(materials, currentStatus);
            }
            //4.2 前进
            path.stepForwardByCurrentStatusAndNum(currentStatus, num);

            //【纵向遍历】
            //5.递归
            currentStatus++;
            backTracingByComposeMaximum(materials, path);

            //6.回溯，撤销处理结果
            //实际只有 Mb 才会发生回撤
            path.backAllMaterialByCurrentStatus(materials, currentStatus);
            currentStatus--;
            if (currentStatus == 0) {
                //无法继续回撤
                return;
            }

            //7.循环迭代
            num++;
        }

    }


    /**
     * 是否已经存在任一物料用完
     *
     * @param materials
     * @return
     */
    private boolean hasRunOut(int[] materials) {
        return materials[0] < 0 || materials[1] < 0 || materials[2] < 0 || materials[3] < 0;
    }

    /**
     * 根据 机器 使用物料
     * 对应机器与物料的使用关系
     *
     * @param materials
     * @param machineStatus
     * @return
     */
    private void runMaterial(int[] materials, int machineStatus) {
        switch (machineStatus) {
            case 1:
                materials[0] = materials[0] - 35;
                materials[1] = materials[1] - 62;
                materials[2] = materials[2] - 15;
                break;
            case 2:
                materials[0] = materials[0] - 18;
                materials[1] = materials[1] - 20;
                materials[2] = materials[2] - 27;
                break;
            case 3:
                materials[0] = materials[0] - 18;
                materials[1] = materials[1] - 21;
                materials[2] = materials[2] - 12;
                materials[3] = materials[3] - 16;
                break;
        }
    }

    /**
     * runMaterial 的反操作
     *
     * @param materials
     * @param machineStatus
     */
    private void backMaterial(int[] materials, int machineStatus) {
        switch (machineStatus) {
            case 1:
                materials[0] = materials[0] + 35;
                materials[1] = materials[1] + 62;
                materials[2] = materials[2] + 15;
                break;
            case 2:
                materials[0] = materials[0] + 18;
                materials[1] = materials[1] + 20;
                materials[2] = materials[2] + 27;
                break;
            case 3:
                materials[0] = materials[0] + 18;
                materials[1] = materials[1] + 21;
                materials[2] = materials[2] + 12;
                materials[3] = materials[3] + 16;
                break;
        }
    }


    /**
     * 根据完成生成的机型生成 cache key
     *
     * @param ma
     * @param mb
     * @param mc
     * @return
     */
    private String generateKey(int ma, int mb, int mc) {
        return String.format("1-%d.2-%d.3-%d.", ma, mb, mc);
    }


    /**
     * 获取下一个状态
     * 状态定义：
     * 1. 造 Ma
     * 2. 造 Mb
     * 3. 造 Mc
     * 假设按照 1->2->3->1... 这样的循环
     *
     * @param currentStatus
     * @return
     */
    private int getNextStatus(int currentStatus) {
        switch (currentStatus) {
            case 1:
                return 2;
            case 2:
                return 3;
            case 3:
                return 1;
        }
        return 0;
    }

    private static int calcMaxNum(int[] currentMaterials, int[] machineThirdBOMArray) {
        int min = 100;
        for (int i = 0; i < 4; i++) {
            if (machineThirdBOMArray[i] > 0) {
                min = Math.min(min, currentMaterials[i] / machineThirdBOMArray[i]);
            }
        }
        return min;
    }

    /**
     * 是否能通过当前的物料数量进行机型制造
     *
     * @param currentMaterials
     * @param machineFirstBOMArray
     */
    private static boolean canUseByCurrentMaterials(int[] currentMaterials, int[] machineFirstBOMArray) {
        return currentMaterials[0] > machineFirstBOMArray[0] && currentMaterials[1] > machineFirstBOMArray[1]
                && currentMaterials[2] > machineFirstBOMArray[2] && currentMaterials[3] > machineFirstBOMArray[3];
    }

    /**
     * 计算各个物料的数量
     */
    @Data
    static class BOMCount {
        private int first;
        private int second;
        private int third;
        private int fourth;
    }

    /**
     * 路径
     */
    @Data
    static class TracePath {

        private int machineFirst;
        private int machineSecond;
        private int machineThird;

        private Deque<Integer> deque = new LinkedList<>();

        public TracePath() {
        }

        public TracePath(int machineFirst, int machineSecond, int machineThird, Deque<Integer> deque) {
            this.machineFirst = machineFirst;
            this.machineSecond = machineSecond;
            this.machineThird = machineThird;
            this.deque = deque;
        }

        public void stepForward(int status) {
            switch (status) {
                case 1:
                    machineFirst++;
                    break;
                case 2:
                    machineSecond++;
                    break;
                case 3:
                    machineThird++;
                    break;
            }
            deque.add(status);
        }

        /**
         * 按照指定机型前进，并设定机型的数量
         *
         * @param currentStatus
         * @param num
         */
        public void stepForwardByCurrentStatusAndNum(int currentStatus, int num) {
            switch (currentStatus) {
                case 1:
                    machineFirst = num;
                    break;
                case 2:
                    machineSecond = num;
                    break;
                case 3:
                    machineThird = num;
                    break;
            }
        }

        public int getCount() {
            return machineFirst + machineSecond + machineThird;
        }

        public int getLastMachineStatus() {
            return deque.peekLast();
        }

        /**
         * 撤销上一个
         */
        public void backOff() {
            if (deque.isEmpty()) {
                throw new RuntimeException("队列为空！无法移除！");
            }
            Integer lastStatus = deque.removeLast();
            switch (lastStatus) {
                case 1:
                    machineFirst--;
                    break;
                case 2:
                    machineSecond--;
                    break;
                case 3:
                    machineThird--;
                    break;
            }
        }

        /**
         * 撤回当前机型的所有数量
         *
         * @param materials
         * @param currentStatus
         */
        private void backAllMaterialByCurrentStatus(int[] materials, int currentStatus) {
            int[] boms = statusArrMap.get(currentStatus);
            int num = 0;
            switch (currentStatus) {
                //当前三层关系中，只需要回撤第二级
                case 2:
                    materials[0] = materials[0] + 18 * machineSecond;
                    materials[1] = materials[1] + 20 * machineSecond;
                    materials[2] = materials[2] + 27 * machineSecond;
                    machineSecond = 0;
                    break;
            }
        }
    }

    @Data
    static class TraceMachine {
        /**
         * 最大层级（一旦达到最大层级：currentLevel == maxLevel，说明本次计算只需要计算最大数量即可！）
         */
        int maxLevel = 3;

        private int machineFirst;
        private int machineSecond;
        private int machineThird;


        /**
         * 当前计算层级
         */
        int currentLevel = 1;

        /**
         * 是否终止
         */
        boolean stop = false;

        /**
         * 前进...好像写错了！说不定还是按照模板来造思路是最好的方式！
         *
         * @param currentMaterials 当前物料情况
         */
        public void stepForward(int[] currentMaterials) {
            currentLevel++;
            if (arriveLastLevel()) {
                //已经到达计算最后一层
                machineThird = calcMaxNum(currentMaterials, machineThirdBOMArray);
                stop = true;
            } else {
                //还不到最后一层
                boolean canUse = false;
                switch (currentLevel) {
                    //如果是第一层
                    case 1:
                        canUseByCurrentMaterials(currentMaterials, machineFirstBOMArray);
                        break;
                    case 2:
                        canUseByCurrentMaterials(currentMaterials, machineSecondBOMArray);
                        break;
                    //...若有其他层，可以继续拓展
                }
                //
            }
        }


        private boolean arriveLastLevel() {
            return currentLevel == maxLevel;
        }
    }

    /**
     * 机型
     */
    @Data
    static class Machine {

        private int bom1;
        private int bom2;
        private int bom3;
        private int bom4;

        public Machine() {
        }

        public Machine(int bom1, int bom2, int bom3, int bom4) {
            this.bom1 = bom1;
            this.bom2 = bom2;
            this.bom3 = bom3;
            this.bom4 = bom4;
        }
    }
}
